package main

import (
	"fmt"
	"math"
)

//给定一个未排序的整数数组，找出最长连续序列的长度。
//要求算法的时间复杂度为 O(n)。
//
//示例:
//输入: [100, 4, 200, 1, 3, 2]
//输出: 4
//解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

func maxSeries(nums []int) int{
	hash_map := map[int] bool{}
	for _, v := range nums{
		hash_map[v] = true
	}
	nLen := 0
	for i, _ := range  nums{
		for nCur, nCurLen := nums[i], 0;;  nCur++{
			if !hash_map[nCur]{
				nLen = int(math.Max(float64(nCurLen), float64(nLen)))
				break
			}else{
				nCurLen++
			}
		}
	}
	return nLen
}

func merge(nums []int) []int{
	if len(nums) < 2{
		return nums
	}
	mid := (len(nums)) >> 1
	return  mergeSort(merge(nums[:mid]), merge(nums[mid:]))
}

func mergeSort(nums0 []int, nums1 []int) []int{
	res := []int{}
	i0, i1 := 0, 0
	len0, len1 := len(nums0), len(nums1)
	for i0 < len0 || i1 < len1{
		if i0 == len0{
			res = append(res, nums1[i1])
			i1++
		}else if i1 == len1{
			res = append(res, nums0[i0])
			i0++
		}else if nums0[i0] < nums1[i1]{
			res = append(res, nums0[i0])
			i0++
		}else{
			res = append(res, nums1[i1])
			i1++
		}
	}
	return  res
}

func main(){
	fmt.Println(maxSeries([]int{100, 4, 200, 1, 3, 2}))
}
